The error correction encoding technique is a technique for protecting data from errors, such as bit inversion, produced on a communication channel during data transmission through the operations of data encoding and decoding, and is now finding extensive use in such fields as digital wireless communication or recording medium. Encoding is the operation of transforming the information for transmission into a codeword having redundant bits appended. Decoding is the operation of estimating the transmitted codeword (information) from the codeword admixed with error (received word) by taking advantage of the redundancy.
As for the error correction code, plural decoding methods are plausible even if the code is the same. Usually, the decoded result is given as a codeword or an information bit string which generates it. There is also known a decoding method comprising estimating the received sequence with weighting. This method is called a soft-output decoding method. The optimal soft-output decoding method outputs conditional probability of respective bits of the information symbol or the codeword, with a received word as the condition, under the constraint condition that the optimum soft-output decoding is a symbol string forming the codeword, and is termed an a posteriori probability decoding method. If the information symbol is binary-valued, it is sufficient for the a posteriori probability decoding to generate L(u(k)) given by the following equation (1):L(u(k))=log(P(u(k)=0|Y)/P(u(k)=1|Y))  (1)
where u(k) is the kth information bit, Y is a received word, and P(u(k)=1|Y) (b=0,1) is a conditional probability that u(k)=b under a condition that a received word is Y.
In 1993, high performance codes, called turbo codes, were proposed. The turbo codes are discussed in great detail in a Publication 1: “Near Shannon limit error-correcting coding and decoding: Turbo codes(1)” (Proceedings of IEEE International Conference of Communications, pp. 1064–1070, 1993). FIG. 7 shows an illustrative structure of a turbo code encoder and a turbo code decoder. Referring to FIG. 7a, the turbo code encoder is basically built using a parallel concatenation of two systematic convolutional encoders 701 and 702, each having a feedback loop, with interposition of an interleaver 703, wherein a memory number not larger than 4 is routinely used. The interleaver 703 is means for reordering a bit sequence. It is noted that the code performance is significantly affected by the size and the designing of the interleaver 703. The parity bits, generated by the convolutional encoders 701 and 702, in conjunction with information bits, are termed elementary codes 1 and 2, respectively.
As shown in FIG. 7b, in the turbo code decoder, decoders 704 and 705 are provided in association with the arrangement of the encoders. The decoder 704 is means for decoding the elementary code 1, whilst the decoder 705 is means for decoding the elementary code 2. As characteristic of the decoding method for the turbo codes, the aforementioned soft-output decoding method is applied to the decoders 704 and 705. The decoder 704(or 705) handles soft-output values for the respective information bits, generated by the decoder 704(or 705), as the a priori information, and decodes the received value with weight applied to the received value. It is noted that the value used as the a priori information in the other decoder is not the value L(u(k)) of the equation (1) per se, but a value Le(u(k)), termed the extrinsic information, represented by the following equation (2):Le(u(k))=L(u(k))−C·y(k)−La(u(k))  (2)
where y(k) is a received value for the information bit u(k), La(u(k)) is the a priori information which, in decoding turbo codes, coincides with the extrinsic information generated by the other decoding means, and C is a constant determined by the S/N ratio of the communication channel. In the iterative decoding of turbo codes, transition to the decoding of the elementary code 2 is made after completion of the elementary code 1. The elementary code 2 is read-in to the decoder 705, with bit reordering performed by the interleaver 706 similar in structure to the interleaver 703, so that the sequence of the information bits of the elementary code 2 in the interleaver 706 will be the same as that in the interleaver 703, for use as the a priori information. The decoder 705 reads-in the received value for the information bits as the sequence thereof is changed by the interleaver 706. In the iterative decoding, the decoding of the elementary code 1 is again performed after the decoding of the elementary code 2 has completely come to a close. In a deinterleaver 707, performing inverse conversion to that in the interleaver 706, the extrinsic information is reordered so that the sequence of the extrinsic information will be coincident with the sequence of the information bits of the elementary code 1. The turbo decoding is featured by the iterative decoding structure in which the extrinsic information is sequentially updated between the two decoders. The decoding error rate is sequentially improved with the progress of the iterative decoding. If the decoding of the elementary codes 1 and 2 is counted as one iteration, a number iterations from 2 to 10 usually suffices. In general, the smaller the SN ratio of the communication channel, the larger the number of iterations must be. The value of L(u(k)) ultimately obtained as the result of the iteration is adopted by hard decision as being the decoded information to terminate the decoding processing.
For developing the decoding device for turbo codes, the designing of the aforementioned soft-input and soft-output device for the convolutional codes is crucial. The soft-input and soft-output decoding of the convolutional codes may be efficiently executed by taking advantage of a trellis structure of the codes. As the soft-input and soft-output decoding algorithm for outputting the value L((u(k)) of the equation (1) by taking advantage of the code trellis, the BCJR algorithm, also termed as MAP algorithm, is known, and is described in greater length in a Publication 2: “Optimal decoding of linear codes for minimizing symbol error rate”(IEEE Transaction on Information Theory, pp. 284–287, 1974). There are also known Max-Log-Map Algorithm and Log-Map algorithms which may reduce the computational complexity by finding an approximate value of L(u(k)) of the equation (1). These algorithms are discussed in greater detail in for example a Publication 3: “A Comparison of optimal and sub-optimal MAP decoding algorithms operating in the Log Domain”(Proceedings of IEEE International Conference of Communications, pp. 1009–1013, 1995).
These algorithms include a processing for finding the probability of reaching each node from the trellis start state (forward value), that is the forward processing, a processing for finding the probability of reaching each node from the trellis end state (backward value), that is the backward processing, and a soft-output generating processing for actually finding the values of the equations (1) and (2), or a soft-output corresponding to its approximate value, by exploiting the forward and backward values, under the conditions of the received sequence and the a priori information. The forward processing is a processing similar to the Viterbi decoding known as the maximum likelihood method for the convolutional codes, and updates the forwards value at forwardly proceeding discrete time points. The backward processing updates the backward values retrogressively as from the trellis end point. The above algorithms differ from the Viterbi decoding as to the necessity of the backward processing.
FIG. 8 illustrates a typical configuration of a turbo code decoder. In FIG. 8, a received data memory 801 stores received values from a demodulator, not shown. An extrinsic information memory 802 stores the extrinsic information of respective information bits previously output in the process of the iterative decoding. A soft-input and soft-output decoding means 803 for elementary codes reads in data from the received data memory 801 and the extrinsic information memory 802 to write the calculated extrinsic information in the extrinsic information memory 802, while executing address conversion for matching to the interleaver as necessary. Since the turbo codes use convolutional codes with a large number of time points, localized decoding which is adapted to exploit a portion of the trellis to produce a successive output, without exploiting the entire trellis, can be realized to enable reduced size of the soft-input and soft-output decoding means 803. In a routine system in which decoding processing is started from the initial point of the trellis, how backward processing is to be carried out poses a problem. In this connection, it has been shown to be sufficient to carry out the backward processing assuming that all states comprise a preset number of time points of the trellis, termed a window. Such processing is discussed in great detail in, for example, a Publication 4: “Soft-output decoding algorithms for continuous decoding of parallel concatenated convolutional codes” (Proceeding of IEEE International Conference on Communications, pp. 112–117, 1996).
In a decoder, it is critical to improve both data throughput, and device size. In a method employing the window as described above, it is desired of the soft-output decoding to output a soft-output each cycle. In a Publication 5: “An intuitive justification on and a simplified implementation of the MAP decoder for convolutional codes” (IEEE Journal on Selected Areas on Communications, pp.260–264, 1998), there is disclosed a method of constructing a decoding schedule by providing backward processing units corresponding to two time points, which are operated with a shift of the time points corresponding to the window size. There has also been proposed in a Publication 6: “VLSI architectures for turbo codes”(IEEE Transactions on VLSI systems, pp.369–379, 1999) a hardware structure consisting in providing a number of backward processing operations corresponding to the number of the window size time points and to pipeline the processing operations. In this device configuration, it is possible to read-in received values in succession to continuously generate soft-output with a delay equal to twice the window size.